Vector Field k-Means: Clustering Trajectories by Fitting Multiple Vector Fields

摘要

Scientists study trajectory data to understand trends in movement patterns,such as human mobility for traffic analysis and urban planning. There is apressing need for scalable and efficient techniques for analyzing this data anddiscovering the underlying patterns. In this paper, we introduce a noveltechnique which we call vector-field $k$-means. The central idea of our approach is to use vector fields to induce asimilarity notion between trajectories. Other clustering algorithms seek arepresentative trajectory that best describes each cluster, much like $k$-meansidentifies a representative "center" for each cluster. Vector-field $k$-means,on the other hand, recognizes that in all but the simplest examples, no singletrajectory adequately describes a cluster. Our approach is based on the premisethat movement trends in trajectory data can be modeled as flows within multiplevector fields, and the vector field itself is what defines each of theclusters. We also show how vector-field $k$-means connects techniques forscalar field design on meshes and $k$-means clustering. We present an algorithm that finds a locally optimal clustering oftrajectories into vector fields, and demonstrate how vector-field $k$-means canbe used to mine patterns from trajectory data. We present experimental evidenceof its effectiveness and efficiency using several datasets, includinghistorical hurricane data, GPS tracks of people and vehicles, and anonymouscall records from a large phone company. We compare our results to previoustrajectory clustering techniques, and find that our algorithm performs fasterin practice than the current state-of-the-art in trajectory clustering, in someexamples by a large margin.